<html>
<head>
    <title>树的遍历</title>
</head>
<body>
    <script>
        /* demo
                    1
                |       | 
                2       3
                |  |     |   |
                4   5    6   7
              |   |
              8   9
        */
        /* 如何用程序生成这样的数据结构呢？ */
        const mockData = {
            val: 1,
            left: {
                val: 2,
                left: {
                    val: 4,
                    left: { val: 8 },
                    right: { val: 9}
                },
                right: {
                    val: 5
                }
            },
            right: {
                val: 3,
                left: { val: 6 },
                right: { val: 7}
            }
        }
        
        function preOrder(tree) {
            var ans = [];
            
            function traverse(tree) {
                if (!tree) return
                ans.push(tree.val);
                traverse(tree.left);
                traverse(tree.right);
            }
            traverse(tree);
            return ans;
        }

        function midOrder(tree) {
            var ans = [];
            
            function traverse(tree) {
                if (!tree) return
                traverse(tree.left);
                ans.push(tree.val);
                traverse(tree.right);
            }
            traverse(tree);
            return ans;
        }

        function postOrder(tree) {
            var ans = [];
            
            function traverse(tree) {
                if (!tree) return
                traverse(tree.left);
                traverse(tree.right);
                ans.push(tree.val);
            }
            traverse(tree);
            return ans;
        }

        // TODO:
        function levelOrder(tree) {
            var ans = [];
            function traverse(tree) {
                if (!tree) return;
                ans.push(tree.left)
                ans.push(tree.right);
            }
        }
    </script>
</body>
</html>